package problems.tsp;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;

import ec.BitBlockIterator;
import ec.BitSolution;
import ec.FitnessEvaluator;
import ec.Solution;

public class TSPFitnessEvaluator implements FitnessEvaluator {

	int NUM_CITIES = 0;
	int MAX_WEIGHT = 0;
	int[][] weights = null;

	private static enum MATRIX_TYPE {
		UPPER_ROW, LOWER_DIAG_ROW
	};

	public static enum SOLUTION_REPRESENTATION {
		AS_PATH(1), AS_PERMUTATOR(2);

		double multiplier = 1;

		private SOLUTION_REPRESENTATION(double multiplier) {
			this.multiplier = multiplier;
		}

		public double getBlockCountAsCityMultiplier() {
			return multiplier;
		}
	};

	public static SOLUTION_REPRESENTATION use_solution_representation;

	private MATRIX_TYPE matrix_type;

	public TSPFitnessEvaluator(String data_file) {
		MATRIX_TYPE t = MATRIX_TYPE.valueOf("LOWER_DIAG_ROW");
		loadWeights(data_file);
	}

	private void loadWeights(String data_file) {
		try {
			BufferedReader file = new BufferedReader(new FileReader(data_file));

			// Get the type of matrix stored in the file
			matrix_type = MATRIX_TYPE.valueOf(file.readLine().split(":")[1]
					.trim());

			// Read in the number of cities
			NUM_CITIES = Integer.parseInt(file.readLine().split(":")[1].trim());
			weights = new int[NUM_CITIES][];

			// Read in optimal fitness
			file.readLine();

			// Read in the matrix
			int NUM_LINES = NUM_CITIES;
			if (matrix_type.equals(MATRIX_TYPE.UPPER_ROW)) {
				NUM_LINES -= 1;
			}

			MAX_WEIGHT = Integer.MIN_VALUE;
			for (int i = 0; i < NUM_LINES; i++) {
				String[] raw_weights = file.readLine().trim().split(" ");

				weights[i] = new int[raw_weights.length];
				for (int j = 0; j < raw_weights.length; j++) {
					weights[i][j] = Integer.parseInt(raw_weights[j]);
					MAX_WEIGHT = Math.max(weights[i][j], MAX_WEIGHT);
				}
			}

			file.close();
		} catch (Exception e) {
			e.printStackTrace();
		}

	}

	@Override
	public double getFitness(Solution solution) {
		double fitness = 0;

		switch (use_solution_representation) {
		case AS_PATH:
			fitness = useSolutionAsPath(solution);
			break;

		case AS_PERMUTATOR:
			fitness = useSolutionAsPermuator(solution);
			break;
		}

		return fitness;
	}

	/**
	 * This method uses the solution as a permutator of the identity path. The
	 * identity path is simply going to each city in sequential order. Any
	 * possible path is a permutation of the identity path. This method takes
	 * two blocks from the solution at a time and uses them as indices for
	 * performing a transposition on the identity path. Given N (where N is the
	 * number of cities) transpositions, any permutation of the identity path
	 * can be reached.
	 * 
	 * @param solution
	 * @return
	 */
	private double useSolutionAsPermuator(Solution solution) {
		BitSolution bits = (BitSolution) solution;

		// Create the initial path that we will permute
		ArrayList<Integer> path = new ArrayList<Integer>(NUM_CITIES);

		// Fill in all the numbers
		for (int i = 0; i < NUM_CITIES; i++) {
			path.add(i);
		}

		// Permute the path
		BitBlockIterator bits_iter = new BitBlockIterator(bits);
		for (int i = 0; i < bits.getNumBlocks(); i += 2) {
			// Grab two indices
			int idx1 = bits_iter.next() % NUM_CITIES;
			int idx2 = bits_iter.next() % NUM_CITIES;

			// Swap the values
			Integer temp = path.get(idx1);
			path.set(idx1, path.get(idx2));
			path.set(idx2, temp);
		}

		return followPath(path.iterator());
	}

	private double useSolutionAsPath(Solution solution) {
		BitSolution bits = (BitSolution) solution;
		BitBlockIterator iter = new BitBlockIterator(bits);
		return followPath(iter);
	}

	private double followPath(Iterator<Integer> iter) {
		int fitness = 0;

		// Keep track of the cities visited (Java sets this to all False for us)
		boolean[] visited = new boolean[NUM_CITIES];

		// The solution is a list of cities to goto, so to evaluate the fitness
		// we follow the path given by the solution. During the traveling we
		// check for illegal paths, such as visiting the same city twice.

		// Get the starting city
		int start_city = iter.next() % NUM_CITIES;
		int current_city = start_city;

		// Follow the path
		while (iter.hasNext()) {
			int city = iter.next() % NUM_CITIES;

			if (visited[city]) {
				// We've already been to the city, so stop following
				break;
			}

			if (current_city == city) {
				// We tried to goto the same city, thats not allowed
				break;
			}

			// Weights is a triangular matrix, so we have to ensure we are
			// accessing within bounds.
			fitness -= getWeight(current_city, city);

			visited[city] = true;
			current_city = city;
		}

		// Add the cost of going back to the start
		fitness -= getWeight(current_city, start_city);
		visited[start_city] = true;

		// Now check that we've visited all the nodes
		for (boolean visit : visited) {
			if (!visit) {
				// We missed a city, so give the penalty of the max weight
				fitness -= MAX_WEIGHT;
			}
		}

		return fitness;
	}

	private int getWeight(int current_city, int target_city) {
		int weight = 0;
		if (current_city != target_city) {
			switch (matrix_type) {
			case LOWER_DIAG_ROW:
				if (target_city > current_city) {
					weight = weights[target_city][current_city];
				} else {
					weight = weights[current_city][target_city];
				}
				break;
			case UPPER_ROW:
				if (current_city > target_city) {
					weight = weights[target_city][current_city - target_city
							- 1];
				} else {
					weight = weights[current_city][target_city - current_city
							- 1];
				}
				break;
			}
		}

		return weight;
	}

	private void printPath(BitSolution bits) {
		BitBlockIterator iter = new BitBlockIterator(bits);

		int current_city = 0;

		// Keep track of the cities visited (Java sets this to all False for us)
		boolean[] visited = new boolean[NUM_CITIES];
		int fitness = 0;
		// The solution is a list of cities to goto, so to evaluate the fitness
		// we follow the path given by the solution. During the traveling we
		// check for illegal paths, such as visiting the same city twice.
		while (iter.hasNext()) {
			int city = iter.next() % (NUM_CITIES - 1);
			System.out.print("City: " + city);

			if (visited[city]) {
				System.out.println("Tried to visit same city twice!");
				break;
			}

			if (current_city == city) {
				System.out.println("Tried to return to current_city!");
				break;
			}

			// Weights is a triangular matrix, so we have to ensure we are
			// accessing within bounds.
			if (current_city > city) {
				fitness -= weights[city][current_city - city - 1];
			} else {
				fitness -= weights[current_city][city - current_city - 1];
			}

			visited[city] = true;
			current_city = city;

			System.out.println(" Fitness=" + fitness);
		}

		// Add the cost of going back to the start
		fitness -= weights[current_city][0];
		System.out.println("Returning to start Fitness=" + fitness);
		visited[0] = true;

		// Now check that we've visited all the nodes
		System.out.println("\nChecking visited cities...");
		for (int i = 0; i < visited.length; i++) {
			if (!visited[i]) {
				// We missed a city, so give the penalty of the max weight
				System.out.println("Failed " + i + " Fitness=" + fitness);
				fitness -= MAX_WEIGHT;
			}
		}
	}

	@Override
	public double getMaxFitness() {
		return 0;
	}

}
